package 集合;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Arrays;
//栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。
//什么是LIFO呢？我们先回顾一下Queue的特点FIFO：
//
//          ────────────────────────
//  (\(\      (\(\    (\(\    (\(\      (\(\
// (='.') ─> (='.')  (='.')  (='.') ─> (='.')
//O(_")")   O(_")") O(_")") O(_")")   O(_")")
//          ────────────────────────
//所谓FIFO，是最先进队列的元素一定最早出队列，而LIFO是最后进Stack的元素一定最早出Stack。如何做到这一点呢？只需要把队列的一端封死：
//
//           ───────────────────────────────┐
//  (\(\       (\(\    (\(\    (\(\    (\(\ │
// (='.') <─> (='.')  (='.')  (='.')  (='.')│
//O(_")")    O(_")") O(_")") O(_")") O(_")")│
//           ───────────────────────────────┘
//因此，Stack是这样一种数据结构：只能不断地往Stack中压入（push）元素，最后进去的必须最早弹出（pop）来：
//
//donuts-stack
//
//Stack只有入栈和出栈的操作：
//-把元素压栈：push(E)；
//-把栈顶的元素“弹出”：pop()；
//-取栈顶元素但不弹出：peek()。
//
//在Java中，我们用Deque可以实现Stack的功能：
//-把元素压栈：push(E)/addFirst(E)；
//-把栈顶的元素“弹出”：pop()/removeFirst()；
//-取栈顶元素但不弹出：peek()/peekFirst()。
//为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。
//当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。
//
//《Stack的作用》
//Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。例如：
//
//static void main(String[] args) {
//    foo(123);
//}
//
//static String foo(x) {
//    return "F-" + bar(x + 1);
//}
//
//static int bar(int x) {
//    return x << 2;
//}
//JVM会创建方法调用栈，每调用一个方法时，先将参数压栈，然后执行对应的方法；当方法返回时，返回值压栈，调用方法通过出栈操作获得方法返回值。
//
//因为方法调用栈有容量限制，嵌套调用过多会造成栈溢出，即引发StackOverflowError：

// 测试无限递归调用
/*public class 使用Stack {
    public static void main(String[] args) {
        increase(1);
    }

    static int increase(int x) {
    	System.out.println(x);
        return increase(x) + 1;
    }
}*/

//我们再来看一个Stack的用途：对整数进行进制的转换就可以利用栈。
//例如，我们要把一个int整数12500转换为十六进制表示的字符串，如何实现这个功能？
//首先我们准备一个空栈：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//└───┘
//然后计算12500÷16=781…4，余数是4，把余数4压栈：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│ 4 │
//└───┘
//然后计算781÷16=48…13，余数是13，13的十六进制用字母D表示，把余数D压栈：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│ D │
//│   │
//│ 4 │
//└───┘
//然后计算48÷16=3…0，余数是0，把余数0压栈：
//
//│   │
//│   │
//│   │
//│ 0 │
//│   │
//│ D │
//│   │
//│ 4 │
//└───┘
//最后计算3÷16=0…3，余数是3，把余数3压栈：
//
//│   │
//│ 3 │
//│   │
//│ 0 │
//│   │
//│ D │
//│   │
//│ 4 │
//└───┘
//当商是0的时候，计算结束，我们把栈的所有元素依次弹出，组成字符串30D4，这就是十进制整数12500的十六进制表示的字符串。

//《计算中缀表达式》
//在编写程序的时候，我们使用的带括号的数学表达式实际上是中缀表达式，即运算符在中间，例如：1 + 2 * (9 - 5)。
//但是计算机执行表达式的时候，它并不能直接计算中缀表达式，而是通过编译器把中缀表达式转换为后缀表达式，例如：1 2 9 5 - * +。
//这个编译过程就会用到栈。我们先跳过编译这一步（涉及运算优先级，代码比较复杂），看看如何通过栈计算后缀表达式。
//计算后缀表达式不考虑优先级，直接从左到右依次计算，因此计算起来简单。首先准备一个空的栈：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//└───┘
//然后我们依次扫描后缀表达式1 2 9 5 - * +，遇到数字1，就直接扔到栈里：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│ 1 │
//└───┘
//紧接着，遇到数字2，9，5，也扔到栈里：
//
//│   │
//│ 5 │
//│   │
//│ 9 │
//│   │
//│ 2 │
//│   │
//│ 1 │
//└───┘
//接下来遇到减号时，弹出栈顶的两个元素，并计算9-5=4，把结果4压栈：
//
//│   │
//│   │
//│   │
//│ 4 │
//│   │
//│ 2 │
//│   │
//│ 1 │
//└───┘
//接下来遇到*号时，弹出栈顶的两个元素，并计算2*4=8，把结果8压栈：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│ 8 │
//│   │
//│ 1 │
//└───┘
//接下来遇到+号时，弹出栈顶的两个元素，并计算1+8=9，把结果9压栈：
//
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│   │
//│ 9 │
//└───┘
//扫描结束后，没有更多的计算了，弹出栈的唯一一个元素，得到计算结果9。
//
//练习
//请利用Stack把一个给定的整数转换为十六进制：

// 转十六进制
/*import java.util.*;

public class 使用Stack {
	public static void main(String[] args) {
		String hex1 = Integer.toHexString(12500);
		
		String hex = toHex(12500);
		System.out.println("hex1: "+hex1+"  hex: "+hex);
		if (hex.equalsIgnoreCase("30D4")) {
			System.out.println("测试通过");
		} else {
			System.out.println("测试失败");
		}
	}

	static String toHex(int n) {

		Stack<String> stack = new Stack<>();

		while (n != 0) {
			int k = n % 16;
			n = n / 16;//取n/16整数部分

			switch(k) {
			case 10 -> stack.push("A");
			case 11 -> stack.push("B");
			case 12 -> stack.push("C");
			case 13 -> stack.push("D");
			case 14 -> stack.push("E");
			case 15 -> stack.push("F");
			default -> stack.push(Integer.toString(k));//k<10
			}
		}

		String result = "";
		int size = stack.size();
		for (int i = 0; i < size; i++) {
			String pop = stack.pop();
			result += pop;
		}

		return result;
	}
}*/

//进阶练习：
//请利用Stack把字符串中缀表达式编译为后缀表达式，然后再利用栈执行后缀表达式获得计算结果：

// 高难度练习，慎重选择！
//import java.util.*;
//
//public class 使用Stack {
//    public static void main(String[] args) {
//        String exp = "1 + 2 * (9 - 5)";
//        SuffixExpression se = compile(exp);
//        int result = se.execute();
//        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
//    }
//
//    static SuffixExpression compile(String exp) {
//        // TODO:
//        return new SuffixExpression();
//    }
//}
//
//class SuffixExpression {
//    int execute() {
//        // TODO:
//        return 0;
//    }
//}

//import java.util.Map;

//import java.util.Stack;
//import java.util.regex.Matcher;
//import java.util.regex.Pattern;
//
///**
// * @author: 默苍璃
// * @date: 2021-09-15 16:14
// *        <p>
// *        请利用Stack把字符串中缀表达式编译为后缀表达式，然后再利用栈执行后缀表达式获得计算结果
// */
//public class 使用Stack {
//
//	public static void main(String[] args) {
//		String exp = "x + 2 * (y - 5)+5";
//		Map<String, Integer> env = Map.of("x", 1, "y", 9);
//		String change = change(exp);//->"x2y5-*+"
//		System.out.println(change);
//		int result = execute(change, env);
//		System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
//	}
//
//	/**
//	 * 中缀表达式转换成后缀表达式 工具类
//	 *
//	 * @param exp
//	 * @return
//	 */
//	static String change(String exp) {
//        // TODO: 1 2 9 5 - * +
//        //判断是否为数字 正则
//		Pattern pattern = Pattern.compile("[0-9xy]");
//        //判断是否为运算符 正则
//		Pattern pattern1 = Pattern.compile("[-+*/]");
//        //返回结果
//		StringBuilder result = new StringBuilder();
//        //储存中间结果的栈（结果栈）
//		Stack<String> s1 = new Stack<>();
//        //运算符栈
//		Stack<String> s2 = new Stack<>();
//
//        //字符串变char[]
//		char[] chars = exp.toCharArray();
////		System.out.println(exp);
////		System.out.println(chars);
//		for (char aChar : chars) {
//			String s = String.valueOf(aChar);
//			System.out.println(s);
//			Matcher matcher = pattern.matcher(s);
//			Matcher matcher1 = pattern1.matcher(s);
//
//            //遇到操作数时，将其压s1(运算符栈)
//			if (matcher.matches()) {
//				s1.push(s);
////				System.out.println("s1="+s1.peek());
//			}
//
//            //遇到运算符
//			if (matcher1.matches()) {
//				
//				while (true) {
//                    //如果s2（运算符栈）为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
//					if (s2.size() == 0 || s2.peek().equals("(")) {
//						s2.push(s);
//						System.out.println("s2="+s2.peek());
//						break;
//					}
//                    //否则，若优先级比栈顶运算符的高，也将运算符压入s2（运算符栈）；
//					if ((s.equals("*") || s.equals("/")) && (s2.peek().equals("+") || s2.peek().equals("-"))) {
//						s2.push(s);
//						break;
//                    //否则，将s2栈顶的运算符弹出并压入到s1中，再次转到与s2中新的栈顶运算符相比较；
//					} else {
//						s1.push(s2.pop());
//					}
//				}//end while
//				
//			}//end if(matcher1.matches())
//
//            //遇到括号时
//            //如果是左括号"("，则直接压入s2（运算符栈）
//			if (s.equals("(")) {
//				s2.push(s);
//			}
//            //如果是右括号")"，则依次弹出s2栈顶的运算符，并压入s1，直到遇到左括号为止，此时将这一对括号丢弃
//			if (s.equals(")")) {
////				System.out.println("s2.size="+s2.size());
//				for (int i = 0; i < s2.size(); i++) {
//					String pop = s2.pop();
////					System.out.println(i+"pop="+pop);
////					System.out.println(!pop.equals("("));
//					if (!pop.equals("(")) {
//						s1.push(pop);
//					}
////					System.out.println(i);
//				}
//			}
//		}
//
//		int size = s2.size();
////		System.out.println("s2.size="+size);
//		for (int i = 0; i < size; i++) {
//			String pop = s2.pop();
//			s1.push(pop);
//		}
//
//		for (String s : s1) {
//			result.append(s);
//		}
////        System.out.println(result.toString());
//		return result.toString();
//	}
//
//	/**
//	 * 中缀表达式 输出结果
//	 *
//	 * @return
//	 */
//	public static int execute(String exp, Map<String, Integer> env) {
//        // TODO:
//        //判断是否为数字 正则
//		Pattern pattern = Pattern.compile("[0-9xy]");
//        //判断是否为运算符 正则
//		Pattern pattern1 = Pattern.compile("[-+*/]");
//        //储存中间结果的栈（结果栈）
//		Stack<String> s1 = new Stack<>();
//
//        //获取变量x y
//		int x = 0;
//		int y = 0;
//		for (Map.Entry<String, Integer> entry : env.entrySet()) {
//			String key = entry.getKey();
//			if (key.equals("x")) {
//				x = entry.getValue();
//			}
//			if (key.equals("y")) {
//				y = entry.getValue();
//			}
//		}
//
//        //字符串变char[]
//		char[] chars = exp.toCharArray();
//		System.out.println(exp);
//		for (char aChar : chars) {
//			String s = String.valueOf(aChar);
//			Matcher matcher = pattern.matcher(s);
//			Matcher matcher1 = pattern1.matcher(s);
//
//            //遇到操作数时，直接扔到栈
//			if (matcher.matches()) {
//				System.out.println(s);
//				s1.push(s);
//			}
//
//            //遇到运算符 弹出栈顶的两个元素，并计算 把结果压栈
//			if (matcher1.matches()) {
//				String x1 = s1.pop();
//				String y1 = s1.pop();
//
//				int i = 0;
//				int j = 0;
//				
//                //x1不是"x"和"y",等于"0-9"
//				if (!x1.equals("x") && !x1.equals("y")) {
//					i = Integer.parseInt(x1);
//				}
//				//y1不是"x"和"y",等于"0-9"
//				if (!y1.equals("x") && !y1.equals("y")) {
//					j = Integer.parseInt(y1);
//				}
//
//				if (x1.equals("x")) {
//					i = x;
//				}
//				if (x1.equals("y")) {
//					i = y;
//				}
//				if (y1.equals("x")) {
//					j = x;
//				}
//				if (y1.equals("y")) {
//					j = y;
//				}
//
//				switch (s) {
//				case "+":
//					s1.push(Integer.toString(j + i));
//					break;
//				case "-":
//					s1.push(Integer.toString(j - i));
//					break;
//				case "*":
//					s1.push(Integer.toString(j * i));
//					break;
//				case "/":
//					s1.push(Integer.toString(j / i));
//					break;
//				default:
//				}
//			}
//
//		}
//		return Integer.parseInt(s1.pop());
//
//	}
//
//}

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

//import static tools.LogUtils.log;
//public class RulesArgsCalcInStack {
public class 使用Stack {
	public static void main(String[] args) {
		String exp = "x+12*(y-5)";
		ArgsSuffixExpression se = compile(exp);
		Map<String, Integer> env = Map.of("x", 1, "y", 9);
		int result = se.execute(env);
//		log.info(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
		System.out.println((exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗")));
	}
	static ArgsSuffixExpression compile(String exp) {
		Deque<String> num = new LinkedList<>();
		Deque<String> opr = new LinkedList<>();
		String[] list = null;
		String regEx = "[^0-9a-zA-Z]";
		String regExOpr = "[^+-/%/*]";

		// 从exp提取数字并入栈
		Pattern p = Pattern.compile(regEx);
		Matcher m = p.matcher(exp);
		System.out.println("m："+m.toString());
		if (m.find()) {
			String sss=m.replaceAll(",");
			String sss1=sss.replaceAll(",+", ",");
			System.out.println("sss："+sss);//x,12,,y,5,
			System.out.println("sss1："+sss1);//x,12,y,5,
			String str = trimChar(m.replaceAll(",").trim().toString().replaceAll(",+", ","), ',');
			System.out.println("找到数字："+str);
			list = str.split(",");
			
			System.out.println("list:"+Arrays.toString(list));//[x, 12, y, 5]
			// log.info(list[1]);
		}

		for (String str : list) {
			// log.info(str);
			num.push(str);
		}

		// 从exp提取运算符号并入栈
		p = Pattern.compile(regExOpr);
		m = p.matcher(exp);
		list = null;
		if (m.find()) {
			String str = trimChar(m.replaceAll(",").trim().toString().replaceAll(",+", ","), ',');
			System.out.println(str);
			list = str.split(",");
			
		}

		for (String operator : list) {
			opr.push(operator);
		}
		return new ArgsSuffixExpression(num, opr);
	}

//去除字符串首尾指定的字符
	public static String trimChar(String str, char ch) {
		if (str.charAt(0) == ch) {
			str = str.substring(1);
		}

		if (str.charAt(str.length() - 1) == ch) {
			str = str.substring(0, str.length() - 1);
		}
		return str;
	}
}

class ArgsSuffixExpression {
	private Deque<String> num = new LinkedList<>();
	private Deque<String> opr = new LinkedList<>();
	public ArgsSuffixExpression(Deque<String> num, Deque<String> opr) {
		this.num = num;
		this.opr = opr;
	}

	// 计算
	int execute(Map<String, Integer> args) {
		int result = 0;
		do {
			String operator = this.opr.pop();
			String num1 = this.num.pop();
			String num2 = this.num.pop();
            //替换x、y参数
			for (String key : args.keySet()) {
				if (num1.equals(key)) {
					num1 = args.get(key).toString();
				}
				if (num2.equals(key)) {
					num2 = args.get(key).toString();
				}
			}
			switch (operator) {
			case "-":
				result = Integer.parseInt(num2) - Integer.parseInt(num1);
				break;
			case "+":
				result = Integer.parseInt(num2) + Integer.parseInt(num1);
				break;
			case "/":
				result = Integer.parseInt(num2) / Integer.parseInt(num1);
				break;
			case "*":
				result = Integer.parseInt(num2) * Integer.parseInt(num1);
				break;
			case "%":
				result = Integer.parseInt(num2) % Integer.parseInt(num1);
				break;
			default:
				throw new IllegalArgumentException("Unexpected operator: " + operator);
			}
			this.num.push(String.valueOf(result));
		} while (this.num.size() > 1);

		System.out.println((this.num.peek()));
		return Integer.valueOf(this.num.peek());
	}
}
